<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
        <html><head>
        <link rel="stylesheet" type="text/css" href="apidocs.css"/>
        <title>API docs for &ldquo;sympy.polys.algorithms&rdquo;</title>
        </head>
        <body><h1 class="module">Module s.p.algorithms</h1><span id="part">Part of <a href="sympy.polys.html">sympy.polys</a></span><div class="toplevel"><div class="undocumented">Undocumented</div></div><table class="children"><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_div">poly_div</a></td><td><div><p>Generalized polynomial division with remainder.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_pdiv">poly_pdiv</a></td><td><div><p>Univariate polynomial pseudo-division with remainder.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_groebner">poly_groebner</a></td><td><div><p>Computes reduced Groebner basis for a set of polynomials.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_lcm">poly_lcm</a></td><td><div><p>Computes least common multiple of two polynomials.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_gcd">poly_gcd</a></td><td><div><p>Compute greatest common divisor of two polynomials.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_gcdex">poly_gcdex</a></td><td><div><p>Extended Euclidean algorithm.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_half_gcdex">poly_half_gcdex</a></td><td><div><p>Half extended Euclidean algorithm.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_resultant">poly_resultant</a></td><td><div><p>Computes resultant of two univariate polynomials.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_subresultants">poly_subresultants</a></td><td><div><p>Computes subresultant PRS of two univariate polynomials.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_sqf">poly_sqf</a></td><td><div><p>Compute square-free decomposition of an univariate polynomial.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.polys.algorithms.poly_decompose">poly_decompose</a></td><td><div><p>Computes functional decomposition of an univariate polynomial.</p>
</div></td></tr></table>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_div">poly_div(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Generalized polynomial division with remainder.

Given polynomial f and a set of polynomials g = (g_1, ..., g_n)
compute a set of quotients q = (q_1, ..., q_n) and remainder r
such that f = q_1*f_1 + ... + q_n*f_n + r, where r = 0 or r is
a completely reduced polynomial with respect to g.

In particular g can be a tuple, list or a singleton. All g_i
and f can be given as Poly class instances or as expressions.

For more information on the implemented algorithm refer to:

[1] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and
    Algorithms, Springer, Second Edition, 1997, pp. 62

[2] I.A. Ajwa, Z. Liu, P.S. Wang, Groebner Bases Algorithm,
    http://citeseer.ist.psu.edu/ajwa95grbner.html, 1995</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_pdiv">poly_pdiv(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Univariate polynomial pseudo-division with remainder.

Given univariate polynomials f and g over an integral domain D[x]
applying classical division algorithm to LC(g)**(d + 1) * f and g
where  d = max(-1, deg(f) - deg(g)),  compute polynomials q and r
such that LC(g)**(d + 1)*f = g*q + r and r = 0 or deg(r) < deg(g).
Polynomials q and r are called the pseudo-quotient of f by g and
the pseudo-remainder of f modulo g respectively.

For more information on the implemented algorithm refer to:

[1] M. Bronstein, Symbolic Integration I: Transcendental
    Functions, Second Edition, Springer-Verlang, 2005</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_groebner">poly_groebner(f, *symbols, **flags):</a></div>
            <div class="functionBody"><pre>Computes reduced Groebner basis for a set of polynomials.

Given a set of multivariate polynomials F, find another set G,
such that Ideal F = Ideal G and G is a reduced Groebner basis.

The resulting basis is unique and has monic generators.

Groebner bases can be used to choose specific generators for a
polynomial ideal. Because these bases are unique you can check
for ideal equality by comparing the Groebner bases.  To see if
one polynomial lies in an ideal, divide by the elements in the
base and see if the remainder vanishes.

They can also be used to  solve systems of polynomial equations
as,  by choosing lexicographic ordering,  you can eliminate one
variable at a time, provided that the ideal is zero-dimensional
(finite number of solutions).

>>> from sympy import *
>>> x,y = symbols('xy')

>>> G = poly_groebner([x**2 + y**3, y**2-x], x, y, order='lex')

>>> [ g.as_basic() for g in G ]
[x - y**2, y**3 + y**4]

For more information on the implemented algorithm refer to:

[1] N.K. Bose, B. Buchberger, J.P. Guiver, Multidimensional
    Systems Theory and Applications, Springer, 2003, pp. 98+

[2] A. Giovini, T. Mora, "One sugar cube, please" or Selection
    strategies in Buchberger algorithm, Proc. ISSAC '91, ACM

[3] I.A. Ajwa, Z. Liu, P.S. Wang, Groebner Bases Algorithm,
    http://citeseer.ist.psu.edu/ajwa95grbner.html, 1995

[4] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and
    Algorithms, Springer, Second Edition, 1997, pp. 62</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_lcm">poly_lcm(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Computes least common multiple of two polynomials.

Given two univariate polynomials,  the LCM is computed  via
f*g = gcd(f, g)*lcm(f, g) formula. In multivariate case, we
compute the unique generator of the intersection of the two
ideals, generated by f and g.  This is done by computing  a
Groebner basis, with respect to any lexicographic ordering,
of t*f and (1 - t)*g, where t is an unrelated symbol and
filtering out solution that does not contain t.

For more information on the implemented algorithm refer to:

[1] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and
    Algorithms, Springer, Second Edition, 1997, pp. 187</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_gcd">poly_gcd(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Compute greatest common divisor of two polynomials.

Given two univariate polynomials, subresultants are used
to compute the GCD.  In multivariate case Groebner basis
approach is used together with f*g = gcd(f, g)*lcm(f, g)
well known formula.

For more information on the implemented algorithm refer to:

[1] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and
    Algorithms, Springer, Second Edition, 1997, pp. 187</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_gcdex">poly_gcdex(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Extended Euclidean algorithm.

Given univariate polynomials f and g over an Euclidean domain,
computes polynomials s, t and h,  such that h = gcd(f, g) and
s*f + t*g = h.

For more information on the implemented algorithm refer to:

[1] M. Bronstein, Symbolic Integration I: Transcendental
    Functions, Second Edition, Springer-Verlang, 2005</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_half_gcdex">poly_half_gcdex(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Half extended Euclidean algorithm.

Efficiently computes gcd(f, g)  and one of the coefficients
in extended Euclidean algorithm. Formally, given univariate
polynomials f and g over an Euclidean domain, computes s
and h, such that h = gcd(f, g) and s*f = h (mod g).

For more information on the implemented algorithm refer to:

[1] M. Bronstein, Symbolic Integration I: Transcendental
    Functions, Second Edition, Springer-Verlang, 2005</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_resultant">poly_resultant(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Computes resultant of two univariate polynomials.

Resultants are a classical algebraic tool for determining if
a  system of n polynomials in n-1 variables have common root
without explicitly solving for the roots.

They are efficiently represented as  determinants of Bezout
matrices whose entries are computed using O(n**2) additions
and multiplications where n = max(deg(f), deg(g)).

>>> from sympy import *
>>> x,y = symbols('xy')

Polynomials x**2-1 and (x-1)**2 have common root:

>>> poly_resultant(x**2-1, (x-1)**2, x)
0

For more information on the implemented algorithm refer to:

[1] Eng-Wee Chionh, Fast Computation of the Bezout and Dixon
    Resultant Matrices, Journal of Symbolic Computation, ACM,
    Volume 33, Issue 1, January 2002, Pages 13-29</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_subresultants">poly_subresultants(f, g, *symbols):</a></div>
            <div class="functionBody"><pre>Computes subresultant PRS of two univariate polynomials.

Polynomial remainder sequence (PRS) is a fundamental tool in
computer algebra as it gives as a sub-product the polynomial
greatest common divisor (GCD), provided that the coefficient
domain is an unique factorization domain.

There are several methods for computing PRS, eg.: Euclidean
PRS, where the most famous algorithm is used, primitive PRS
and, finally, subresultants which are implemented here.

The Euclidean approach is reasonably efficient but suffers
severely from coefficient growth.  The primitive algorithm
avoids this but requires a lot of coefficient computations.

Subresultants solve both problems and so it is efficient and
have moderate coefficient growth. The current implementation
uses pseudo-divisions  which is well suited for coefficients
in integral domains or number fields.

Formally,  given univariate polynomials f and g over an UFD,
then a sequence (R_0, R_1, ..., R_k, 0, ...) is a polynomial
remainder sequence where R_0 = f, R_1 = g, R_k != 0 and R_k
is similar to gcd(f, g).

For more information on the implemented algorithm refer to:

[1] M. Bronstein, Symbolic Integration I: Transcendental
    Functions, Second Edition, Springer-Verlang, 2005

[2] M. Keber, Division-Free computation of subresultants
    using Bezout matrices, Tech. Report MPI-I-2006-1-006,
    Saarbrucken, 2006</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_sqf">poly_sqf(f, *symbols):</a></div>
            <div class="functionBody"><pre>Compute square-free decomposition of an univariate polynomial.

Given an univariate polynomial f over an unique factorization domain
returns tuple (f_1, f_2, ..., f_n),  where all  A_i are co-prime and
square-free polynomials and f = f_1 * f_2**2 * ... * f_n**n.

>>> from sympy import *
>>> x,y = symbols('xy')

>>> p, q = poly_sqf(x*(x+1)**2, x)

>>> p.as_basic()
x
>>> q.as_basic()
1 + x

For more information on the implemented algorithm refer to:

[1] M. Bronstein, Symbolic Integration I: Transcendental
    Functions, Second Edition, Springer-Verlang, 2005

[2] J. von zur Gathen, J. Gerhard, Modern Computer Algebra,
    Second Edition, Cambridge University Press, 2003</pre></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.polys.algorithms.poly_decompose">poly_decompose(f, *symbols):</a></div>
            <div class="functionBody"><pre>Computes functional decomposition of an univariate polynomial.

Besides factorization and square-free decomposition, functional
decomposition is another important, but very different,  way of
breaking down polynomials into simpler parts.

Formally given an univariate polynomial f with coefficients in a
field of characteristic zero, returns tuple (f_1, f_2, ..., f_n)
where f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n)) and f_2, ...,
f_n are monic and homogeneous polynomials of degree at least 2.

Unlike factorization, complete functional decompositions of
polynomials are not unique, consider examples:

 [1] f o g = f(x + b) o (g - b)
 [2] x**n o x**m = x**m o x**n
 [3] T_n o T_m = T_m o T_n

where T_n and T_m are Chebyshev polynomials.

>>> from sympy import *
>>> x,y = symbols('xy')

>>> p, q = poly_decompose(x**4+2*x**2 + y, x)

>>> p.as_basic()
y + 2*x + x**2
>>> q.as_basic()
x**2

For more information on the implemented algorithm refer to:

[1] D. Kozen, S. Landau, Polynomial decomposition algorithms,
    Journal of Symbolic Computation 7 (1989), pp. 445-456</pre></div>
            </div></body>
        